There are a couple of nice examples in Russell and Norwig.

It's very worth reading.

So there's a huge literature about Bayesian networks,

because they're really, really, really useful in practice.

So we can do probabilistic inference on them

exactly if they are of very easy shape, which allows us

to compute exactly the probability of a couple

of distribution over a couple of random variables,

given some edivents, which is exactly the inference problem

an agent has when it prepares its next action.

We have a couple of exact methods.

They work well for easy, simple Bayesian networks.

And if we have a realistic network that

is multiply connected, typically with some diamond situations,

then we have to do more interesting things.

Generally, sampling helps.

That works slightly like Monte Carlo trees.

There's a clustering technique.

If you kind of have a nice tree, and then you

have this nasty diamond in it, what

you can do is you can just pretend it doesn't exist

and make it into a big node.

And if you have a couple of little nasty things, that helps.

And of course, I'm waving my hands here

to really get it going.

By now, it's probably a master's thesis.

At that time, it was a PhD thesis,

so something you worked three years on to actually have

it work.

And you can read up on it in an hour in Russell and Norwegan

and understand it.

You can, as always, compile Bayesian networks

into SAT problems.

Essentially, the same complexity class.

It'll blow up a little bit, but essentially what you do

is you kind of discretize it, give the situations

that you come into creative names,

and then you apply DPLL on it.

And that works surprisingly well.

I think I told you when we were talking about planning,

when this first compile to SAT idea came along in the 80s

and blew every other algorithm out of the water,

there was a whole cottage industry of,

oh, let's take any other algorithm

and put it in the same place.

There was a whole cottage industry of, oh, let's take any other NP

complete problem and compile it to SAT as well.

Professors had the same idea everywhere,

just saying, oh, the next PhD student that comes along,

he'll do SAT compilation or she.